6959. Запрос Суммы на Отрезке

Список L содержит n целых чисел. Найдите сумму чисел на отрезке между индексами i и j включительно, то есть

RSQ(i, j) = L[i] + L[i + 1] + L[i + 2] + ... + L[j]

Вход. Первая строка содержит количество тестов t (1 ≤ t ≤ 5). Каждый тест начинается с пустой строки, за которой следует строка с двумя целыми числами n и q (1 ≤ n, q ≤ 10⁵). Следующая строка содержит n неотрицательных целых чисел, каждое из которых не больше 10⁹. Затем следуют q строк, каждая из которых содержит два целых числа i и j (0 ≤ i, j < n).

Выход. Для каждого запроса выведите в отдельной строке значение RSQ(i, j). Ответы для разных тестов разделяйте пустой строкой.

Пример входа	Пример выхода
2 10 8 1 2 3 4 5 6 7 8 9 10 4 4 3 8 0 3 1 3 2 9 8 9 6 8 5 7 10 5 10 9 7 20 14 23 14 27 38 77 3 6 7 9 6 7 1 5 4 8	5 39 10 9 52 19 24 21 71 142 41 73 116

РЕШЕНИЕ

последовательности, частичные суммы

Анализ алгоритма

По входному списку чисел L₁, …, L_n построим массив частичных сумм

s₁ = L₁,

s₂ = L₁ + L₂,

…

s_n = L₁ + L₂ + … + + L_n

Тогда

RSQ(i, j) = L[i] + L[i + 1] + L[i + 2] + ... + L[j] = s_j – s_i-1

Реализация алгоритма

Частичные суммы будем вычислять “на лету” при чтении входного списка чисел L и сохранять их в массиве s.

#define MAX 100010

long long s[MAX];

Читаем входные данные.

scanf("%d",&tests);

while(tests--)

{

scanf("%d %d",&n,&q);

scanf("%lld",&s[1]);

Заполним массив частичных сумм s.

for(i = 2; i <= n; i++)

{

scanf("%lld",&s[i]);

s[i] += s[i-1];

}

Последовательно обрабатываем q запросов. Поскольку индексы a и b в запросах RSQ(a, b) начинаются с нуля, а массив частичных сумм s строится с индекса 1, то для каждого запроса ответ находим слудующим образом:

RSQ(a, b) = s_b+1 – s_a.

for(i = 0; i < q; i++)

{

scanf("%d %d",&a,&b);

printf("%lld\n",s[b+1] - s[a]);

}

Ответы для соседних тестов разделяются пустой строкой.

if (tests > 0) printf("\n");

}

Реализация алгоритма – алгоритм МО

#include <cstdio>

#include <vector>

#include <cmath>

#include <algorithm>

using namespace std;

int tests, n, q, a, b, i, block, curL, curR, l, r;

vector<long long> s, ans;

long long sum;

struct queries

{

int l, r, idx;

};

vector<queries> query;

int f(queries a, queries b)

{

if ((a.l / block) == (b.l / block))

//return a.r < b.r;

return (a.l / block % 2 == 0) ? a.r < b.r : a.r > b.r;

return a.l < b.l;

}

int main(void)

{

scanf("%d", &tests);

while (tests--)

{

scanf("%d %d", &n, &q);

s.clear(); s.resize(n);

for (i = 0; i < n; i++)

scanf("%lld", &s[i]);

query.clear(); query.resize(q);

for (i = 0; i < q; i++)

{

scanf("%d %d", &query[i].l, &query[i].r);

query[i].idx = i;

}

block = sqrt(n);

sort(query.begin(), query.end(), f);

curL = 0; curR = -1; sum = 0;

ans.clear(); ans.resize(q);

for (i = 0; i < query.size(); i++)

{

l = query[i].l;

r = query[i].r;

while (curL < l)

{

sum -= s[curL];

curL++;

}

while (curL > l)

{

curL--;

sum += s[curL];

}

while (curR < r)

{

curR++;

sum += s[curR];

}

while (curR > r)

{

sum -= s[curR];

curR--;

}

ans[query[i].idx] = sum;

}

for (i = 0; i < ans.size(); i++)

printf("%lld\n", ans[i]);

printf("\n");

}

return 0;

}